package d2;
import java.util.*;

public class Day15 {
    public static void main(String[] args) {
        int[][] a = {{1,0}};
                findOrder(2,a);
    }
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        int n=numCourses;
        int[] nums = new int[n];
        int[] in = new int[n];//记录入度
        //1.建立邻接矩阵
        Map<Integer,List<Integer>> map= new HashMap<>();
        for(int i=0;i<prerequisites.length;i++) {
            int a=prerequisites[i][0],b=prerequisites[i][1];//b--a
            if(!map.containsKey(b)) map.put(b,new ArrayList<>());
            map.get(b).add(a);
            in[a]++;
        }
        Queue<Integer> q = new LinkedList<>();
        //2.键图
        for(int i=0;i<n;i++) {
            if(in[i]==0) q.add(i);
        }
        //3.
        int i=0;
        while (!q.isEmpty()) {
            int t = q.poll();
            nums[i++]=t;
            for(int x:map.getOrDefault(t,new ArrayList<>())) {
                in[x]--;
                if(in[x]==0) q.add(x);
            }
        }
        for(int x:in) {
            if(x!=0) return new int[0];
        }
        return nums;
    }
}
